/*
 * @author zzr
 * @date: 2025/10/17  18:51
 * @description: 判断当前的树是否为平衡二叉树
 * 平衡二叉树：每个节点的左子树和右子树的高度差的绝对值不超过1
 * 并且左右子树也都是平衡二叉树
 */
public class Demo23 {


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

//    public int getHeight(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        int left = getHeight(root.left);
//        int right = getHeight(root.right);
//
//        return left > right ? left + 1 : right + 1;
//    }
//
//    public boolean isBalanced(TreeNode root) {
//        if (root == null) {
//            return true;
//        }
//
//        int left = getHeight(root.left);
//        int right = getHeight(root.right);
//
//        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
//    }


    /**
     * 在进行求高度的时候，就已经可以知道树是否平衡了~~~
     */

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);

        if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
            return Math.max(left, right) + 1;
        } else {
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getHeight(root) > 0;
    }
}
